export class OrderedSet<T> {
    private values: T[] = []; // 存储有序值
    private valueToIndex: Map<T, number> = new Map(); // 值到索引的映射

    constructor(private comparator: (a: T, b: T) => number = (a: T, b: T) => {
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    }) {
    }

    /**
     * 添加元素到有序集合
     */
    add(value: T): boolean {
        // 如果值已存在，直接返回
        if (this.valueToIndex.has(value)) {
            return false;
        }

        // 找到插入位置
        let insertIndex = this.values.length;
        for (let i = 0; i < this.values.length; i++) {
            if (this.comparator(value, this.values[i]) < 0) {
                insertIndex = i;
                break;
            }
        }

        // 插入值
        this.values.splice(insertIndex, 0, value);

        // 更新索引映射
        this.updateIndicesFrom(insertIndex);

        return true;
    }

    /**
     * 删除元素
     */
    delete(value: T): boolean {
        const index = this.valueToIndex.get(value);
        if (index === undefined) {
            return false;
        }

        // 删除值
        this.values.splice(index, 1);

        // 从映射中删除
        this.valueToIndex.delete(value);

        // 更新受影响元素的索引
        this.updateIndicesFrom(index);

        return true;
    }

    /**
     * 检查是否包含元素
     */
    has(value: T): boolean {
        return this.valueToIndex.has(value);
    }

    /**
     * 获取元素排名（索引），O(1) 复杂度
     */
    getRank(value: T): number {
        const index = this.valueToIndex.get(value);
        return index !== undefined ? index : -1;
    }

    /**
     * 获取排名对应的元素
     */
    getByRank(rank: number): T | undefined {
        return this.values[rank];
    }

    /**
     * 获取集合大小
     */
    get size(): number {
        return this.values.length;
    }

    /**
     * 清空集合
     */
    clear(): void {
        this.values = [];
        this.valueToIndex.clear();
    }

    /**
     * 转换为数组
     */
    toArray(): T[] {
        return [...this.values];
    }

    /**
     * 获取最小值
     */
    get min(): T | undefined {
        return this.values[0];
    }

    /**
     * 获取最大值
     */
    get max(): T | undefined {
        return this.values[this.values.length - 1];
    }

    /**
     * 从指定位置开始更新索引映射
     */
    private updateIndicesFrom(startIndex: number): void {
        for (let i = startIndex; i < this.values.length; i++) {
            this.valueToIndex.set(this.values[i], i);
        }
    }

    /**
     * 迭代器
     */
    [Symbol.iterator](): Iterator<T> {
        return this.values[Symbol.iterator]();
    }

    /**
     * 遍历方法
     */
    forEach(callback: (value: T, index: number, set: OrderedSet<T>) => void): void {
        this.values.forEach((value, index) => callback(value, index, this));
    }
}